class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val = val;
    }
  }

public class Test {
    /*
    题目 1：判断一个链表是否为回文结构
     */
    private static ListNode midNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

    public static boolean isPail (ListNode head) {
        ListNode slow = midNode(head);
        //翻转
        ListNode cur = slow.next;
        ListNode curNext = null;

        while(cur != null){
            curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //进行数值的比较
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }

            if(head.next == slow){
                return true;
            }

            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    public static void main1(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(2);
        ListNode node6 = new ListNode(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        boolean rest = isPail(node1);
    }

    /*
    题目 2：二分查找Ⅰ
     */
    public int search (int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /*
    题目 3：二维数组中的查找
     */
    public static boolean Find(int target, int [][] array) {
        if(array.length == 0 || array[0].length == 0){
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;

        while(i < array.length && j >= 0){
            if(array[i][j] > target){
                j--;
            }else if(array[i][j] < target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }

    /*
    题目 4：寻找峰值
     */
    //自己的思路，略显繁琐！
    public int findPeakElement1 (int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int peak = -1;
        for(int i = 0; i < nums.length; i++){
            if(i == 0){
                if(nums[i + 1] < nums[i])
                    return i;
            }


            if(i == nums.length - 1){
                if(nums[i] > nums[i - 1]){
                    return i;
                }
            }

            if(nums[i] > nums[i + 1] && nums[i] > nums[i - 1]){
                return i;
            }
        }
        return -1;
    }

    //为什么二分查找能够成功？？？
    //给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
    // 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
    // 2.假设 nums[-1] = nums[n] = −∞
    // 3.对于所有有效的 i 都有 nums[i] != nums[i + 1] 这个条件非常关键！！
    // 4.你可以使用O(logN)的时间复杂度实现此问题吗？————二分查找法
    public static int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < nums[mid + 1]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }

    /*
    题目 5：数组中的逆序对
     */



}
